package 剑指offer.数组;

import java.util.Arrays;

/**
 * 本题特点：数组是排序的
 * 解法：二分查找
 * <p>
 * 二分法查找不一定要把数组一分为二，然后左右递归寻找
 * 也可以只处理指针，让指针左右移动
 */
public class 第53题在排序数组中查找数字 {

    /**
     * 题目一：数字在排序数组中出现的次数
     * 输入：1,2,3,3,3,3,4,5 以及数字 3
     * 输出：4
     * <p>
     * <p>
     * 解法：找到第一个出现 k 的索引，和最后一个出现 k 的索引，大的减小的就行了
     */
    public static int GetNumberOfK(int[] array, int k) {
        int index = Arrays.binarySearch(array, k);
        int count = 1;
        if (index < 0) {
            return 0;
        } else {
            for (int i = index + 1; i < array.length; i++) {
                if (array[i] == k) {
                    count++;
                }
            }

            for (int i = index - 1; i >= 0; i--) {
                if (array[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 题目二：0 ~ n-1 中有一个数字不在这个数组里面
     * 该数组单调递增
     * 找出这个缺失的数
     * <p>
     * 解法：数组既然是有序的，遍历就是最傻的办法
     * 需要使用二分法来快速寻找丢失的数据
     */
    public static int findMissNumber(int[] array, int n) {
        // 数组index为0的位置存储的就是0，要是丢失一个数据，则从该数据开始所有的数据将会错位
        // 假设丢失的数据是 m，则 array[m] != m，基于这个条件做二分查找
        int start = 0;
        int end = n - 1;
        while (start <= end) {
            int mid = (end + start) >> 1;
            if (array[mid] != mid) {
                if (mid == 0 || array[mid - 1] == mid - 1) {
                    return mid;
                } else {
                    end = mid - 1;
                }
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 数组递增，找出任意一个index等于数值的元素
     * <p>
     * 如：-3,-1,1,3,5 中 3 的 index 等于数值
     */
    public static int elementEqualsIndex(int[] array) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (array[mid] == mid)
                return mid;
            else {
                if (array[mid] > mid) {
                    // 往前找
                    end = mid - 1;
                } else {
                    // 往后找
                    start = mid + 1;
                }
            }
        }
        return 2147183647;
    }

    public static void main(String[] args) {
//        int[] array = {1, 3, 3, 3, 3, 4, 5};
//        System.out.println(GetNumberOfK(array, 2));

//        System.out.println(findMissNumber(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8}, 9));

        System.out.println(elementEqualsIndex(new int[]{-3, -1, 1, 3, 4, 5}));
    }
}
